package com.eloancn.leecode.classic;

import java.util.Stack;

import org.junit.Test;

/**
 * 链表反转
 * @author lihepeng
 *
 */
public class RevertLink {
	/**
	 * 反转链表 fuc1
	 * 借助堆栈结构完成业务
	 * @param node
	 * @return
	 */
	public Node revertfuc(Node node) {
		Stack<Node> stack = new Stack<>();
		while(node!=null) {
			stack.push(node);
			node = node.getNext();
		}
		Node currentNode = null;
		Node lastNode = null;
		while(!stack.isEmpty()) {
			Node node2 = stack.pop();
			if (currentNode ==null) {
				currentNode = node2;
				lastNode = currentNode;
			}else {
				node2.setNext(null);
				currentNode.setNext(node2);
				currentNode = node2;
			}
		}
		
		return lastNode;
	}
	/**
	 * 链表的头部插入
	 */
	public Node headerInsert(Node newNode,Node currentNode) {
		newNode.setNext(currentNode);
		return newNode;
	}
	
	/**
	 * 反转链表方法2
	 * 遍历反转
	 * @return
	 */
	public Node revertFuc2(Node headNode) {
		if (headNode ==null) {
			return headNode;
		}
		Node pre = headNode;
		Node currentNode = headNode.getNext();
		Node tem = null;
		while(currentNode!=null) {
			tem = currentNode.getNext();
			currentNode.setNext(pre);
			pre = currentNode;
			currentNode = tem;
		}
		headNode.setNext(null);
		return pre;
		
	}
	@Test
	public void runFunc() {
		Node node = new Node("1");
		Node node1 = new Node("2");
		Node node2 = new Node("3");
		Node node3 = new Node("4");
		Node node4 = new Node("5");
		node.setNext(node1);
		node1.setNext(node2);
		node2.setNext(node3);
		node3.setNext(node4);
		Node nodex =  this.revertFuc2(node);
		printNode(nodex);
		
	}
	public void printNode(Node node) {
		StringBuffer sb = new StringBuffer();
		while (node!= null) {
			sb.append(node.getValue());
			sb.append("->");
			node = node.getNext();
		}
		System.out.println(sb.toString());
	}
	// 头部插入测试
	@Test
	public void runTest03() {
			Node head = new Node("1");
			Node headerInsert = this.headerInsert(new Node("2"), head);
			this.printNode(headerInsert);
			
	}
}



class Node{
	private String value;
	private Node next;
	public Node(String value) {
		super();
		this.value = value;
	}
	public Node getNext() {
		return next;
	}
	public void setNext(Node next) {
		this.next = next;
	}
	public String getValue() {
		return value;
	}
	public void setValue(String value) {
		this.value = value;
	}
	
	
}
